// https://leetcode.cn/problems/course-schedule/

// 题干：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
//      在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，
//      其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
//      例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
//      请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

// 示例：输入：numCourses = 2, prerequisites = [[1,0]]
//      输出：true

// 碎语：BFS解决拓扑排序
//       1.有向无环图：入度：有多少边指向它 ；出度：有多少边它指向
//       2.AOV网：顶点活动图：在有向无环图中，用顶点来表示一个活动，用边来表示活动的先后顺序的图结构
//       3.拓扑排序：找到做事情的先后顺序
//       4.实现拓扑排序：
//                (1)找出图中入度为0的点，然后输出
//                (2)删除与该点连接的边
//                (3)重复1，2操作，直到图中没有点或者没有入度为0的点为止（避免成环）
//       借助队列，来一次BFS即可
//       初始化，把所有入度为0的点加入到队列中
//       当队列不为空的时候，拿出队头元素，加入到最终结果中
//       删除与该元素相连的边
//       判断：与删除边相连的点，是否入度变成0，如果入度为0，加入到队列中
#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        // 如何建图？灵活使用语言提供的容器
        // 看稠密（看数据量）邻接矩阵 邻接表

        // 1.准备工作
        int n = numCourses;
        unordered_map<int, vector<int>> edges; // 邻接表存图
        vector<int> in(n); // 标记每一个定义的入度

        // 2.建图
        for (const auto& e : prerequisites){
            int a = e[0], b = e[1]; // b -> a
            edges[b].push_back(a); // 把边存到邻接表中
            in[a]++;
        }

        // 3.拓扑排序
        queue<int> q;

        // 把所有入度为0的点加入到队列中
        for (int i = 0 ; i < n ; i++){
            if (in[i] == 0) q.push(i);
        }

        // 来一次BFS
        while (q.size()){
            int t = q.front(); q.pop();
            for (const int& a : edges[t]){
                in[a]--;
                if (in[a] == 0) q.push(a);
            }
        }

        // 判断是否有环
        for (int i = 0 ; i < n ; i++){
            if (in[i]) return false;
        }

        return true;
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> prerequisites = {{1, 0}};

    cout << sol.canFinish(2, prerequisites) << endl;

    return 0;
}